package newcoder_exp.justPractise;
import java.util.*;
import org.junit.*;
import tree.*;
public class NC60 {
    public class Solution {

        //判断一棵树是否是平衡二叉树与搜索二叉树
        public boolean[] judgeIt (TreeNode root) {
            boolean[] res = new boolean[2];
            res[0] = isBST(root);

            Queue<TreeNode> queue = new LinkedList<>();
            if (root == null) {
                res[1] = true;
                return res;
            }
            queue.offer(root);
            boolean start = false;
            int n;
            TreeNode cur;
            while (!queue.isEmpty()) {
                n = queue.size();
                // start = false;
                for (int i = 0; i < n; i++) {
                    cur = queue.poll();
                    if (start) {
                        if (cur.left != null || cur.right != null) {
                            res[1] = false;
                            return res;
                        }
                    } else {
                       if (cur.left == null && cur.right != null) {
                            res[1] = false;
                            return res;
                       } else if (cur.left != null && cur.right == null) {
                           queue.offer(cur.left);
                           start = true;
                       } else if (cur.left == null && cur.right == null) {
                           start = true;
                       } else {
                           queue.offer(cur.left);
                           queue.offer(cur.right);
                       }
                    }
                }
            }
            res[1] = true;
            return res;
        }

        public boolean isBST(TreeNode root) {
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root;
            int last = Integer.MIN_VALUE;
            while (cur != null || !stack.isEmpty()) {
                while (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                }
                cur = stack.pop();
                if (last > cur.val) return false;
                last = cur.val;
                cur = cur.right;
            }
            return true;
        }
    }


    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums = new int[]{};
        TreeNode root = TreeUtils.deserialization("{107,29,89,130,12,109,85,86,52,74,121,106,122,141,65,50,28,118,61,99,57,7,25,148,4,69,151,20,142,32,120,71,117,45,83,58,19,53,60,157,101,76,125,35,3,110,96,139,145,108,27,116,135,81,6,8,150,41,127,64,43,156,104,9,1,126,14,51,22,26,67,21,153,75,143,34,2,159,158,154,94,46,147,49,15,123,70,47,16,87,59,62,138,72,97,124,144,80,90,36,149,23,160,33,44,10,114,79,54,134,129,131,82,77,115,55,39,88,68,73,5,92,38,132,24,17,40,98,146,31,100,66,137,13,63,128,84,11,119,102,103,95,152,30,105,37,78,113,91,140,155,111,18,136,42,161,133,93,48,112,56}");
        TreeNode root2 = TreeUtils.deserialization("{65536,32768,83979,16384,49152,75787,92171,8192,24576,40960,57344,71691,79883,88075,96267,4096,12288,20480,28672,36864,45056,53248,61440,69632,73739,77835,81931,86027,90123,94219,98315,2048,6144,10240,14336,18432,22528,26624,30720,34816,38912,43008,47104,51200,55296,59392,63488,67584,70667,72715,74763,76811,78859,80907,82955,85003,87051,89099,91147,93195,95243,97291,99339,1024,3072,5120,7168,9216,11264,13312,15360,17408,19456,21504,23552,25600,27648,29696,31744,33792,35840,37888,39936,41984,44032,46080,48128,50176,52224,54272,56320,58368,60416,62464,64512,66560,68608,70155,71179,72203,73227,74251,75275,76299,77323,78347,79371,80395,81419,82443,83467,84491,85515,86539,87563,88587,89611,90635,91659,92683,93707,94731,95755,96779,97803,98827,99851,512,1536,2560,3584,4608,5632,6656,7680,8704,9728,10752,11776,12800,13824,14848,15872,16896,17920,18944,19968,20992,22016,23040,24064,25088,26112,27136,28160,29184,30208,31232,32256,33280,34304,35328,36352,37376,38400,39424,40448,41472,42496,43520,44544,45568,46592,47616,48640,49664,50688,51712,52736,53760,54784,55808,56832,57856,58880,59904,60928,61952,62976,64000,65024,66048,67072,68096,69120,69899,70411,70923,71435,71947,72459,72971,73483,73995,74507,75019,75531,76043,76555,77067,77579,78091,78603,79115,79627,80139,80651,81163,81675,82187,82699,83211,83723,84235,84747,85259,85771,86283,86795,87307,87819,88331,88843,89355,89867,90379,90891,91403,91915,92427,92939,93451,93963,94475,94987,95499,96011,96523,97035,97547,98059,98571,99083,99595,100107,256,768,1280,1792,2304,2816,3328,3840,4352,4864,5376,5888,6400,6912,7424,7936,8448,8960,9472,9984,10496,11008,11520,12032,12544,13056,13568,14080,14592,15104,15616,16128,16640,17152,17664,18176,18688,19200,19712,20224,20736,21248,21760,22272,22784,23296,23808,24320,24832,25344,25856,26368,26880,27392,27904,28416,28928,29440,29952,30464,30976,31488,32000,32512,33024,33536,34048,34560,35072,35584,36096,36608,37120,37632,38144,38656,39168,39680,40192,40704,41216,41728,42240,42752,43264}");
        TreeNode root3 = TreeUtils.deserialization("{3,2,5,1,4}");



        System.out.println(Arrays.toString(        s.judgeIt(root3)));
    }
}
